"""
汉诺塔来源于印度传说的一个故事，
上帝创造世界时作了三根金刚石柱子，在一根柱子上从上往下从小到大顺序摞着 64 片黄金圆盘。
上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘，只能移动在最顶端的圆盘。
有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。
也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。
当然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。
"""
"""
将盘片塔从开始柱，经由中间柱，移动到目标柱：
    首先将上层 N-1 个盘片的盘片塔，从开始柱，经由目标柱，移动到中间柱；
    然后将第N个（最大的）盘片，从开始柱，移动到目标柱。
    最后将放置在中间柱的 N-1 个盘片的盘片塔，经由开始柱，移动到目标柱。
基本结束条件，也就是最小规模问题变为：1个盘片的移动问题
"""


def move_tower(height, start_pole, mid_pole, target_pole):
    if height >= 1:
        # 开始柱 目标柱 中间柱
        move_tower(height - 1, start_pole, target_pole, mid_pole)
        # 记录移动
        move_disk(height, start_pole, target_pole)
        # 中间柱  开始柱  目标柱
        move_tower(height - 1, mid_pole, start_pole, target_pole)


def move_disk(disk, start_pole, target_pole):
    print(f"将 {disk} 号盘子从 {start_pole}号柱 移到 {target_pole}号柱")


move_tower(3, "1", "2", "3")  # 2^n - 1次
print("移动完成！")
